//快速排序实现
int split(int *a,int low,int high){
	int i =low;
	int x = a[i];
	for(int j=i+1;j<=high;j++){
        //如果当前元素小于基准元素
		if(a[j] <= x){
            //应该放在基准元素左边，根据慢指针进行填充
            //并将可能不属于左边的元素换到后面去
			i++;
			swap(a[i],a[j]);
			}
	}
    //交换基准元素与最后一个小于等于基准元素的值
    swap(a[low],a[i]);
	return i;
} 

int partitiion(int *a,int low,int high){
	int x=a[low];
	int i =low,j=high;
	while(i<j){
        //从右到左找第一个小于等于基准的值
		while(i<j && a[j]>=x){
			j--;
		}
        //从左到右找第一个大于等于基准的值
		while(i<j && a[i]<=x){
			i++;
		}
        //如果不是指向同一个位置则说明还未处理完，交换元素
		if(i!=j){
			swap(a[i],a[j]);
		}
	}
    //i==j 已经遍历完
	swap(a[low],a[i]);
	return i;
	}
	
void quickSort(int *a,int low,int high){
	if(low < high){
		int par = partitiion(a,low,high);
        cout<<"这次分隔的par是"<<par<<endl;
		quickSort(a,0,par-1);
		quickSort(a,par+1,high);	
	}
}